#include <stdio.h>
#define swap(a,b) {a=a+b; b=a-b; a=a-b;}	


int max_index(int arr[], int len, int parent_index)
{
	int lchild_index, rchild_index, max;
	lchild_index = parent_index*2+1;
	rchild_index = parent_index*2+2;
	if (lchild_index < len && arr[lchild_index] > arr[parent_index]) 
		max = lchild_index;
	else max = parent_index; //lchild is not exist or smaller than parent
	if (rchild_index < len && arr[rchild_index] > arr[max]) 
		max = rchild_index;
	
	return max;
}

void down(int arr[], int len, int i)
{
	int max = max_index(arr,len,i);
	if (max == i) return ;	
	
	swap(arr[i],arr[max]);
	down(arr,len,max);
}

int heap_sort(int arr[], int len)
{
	int i;
	for (i = (len-1)/2; i >= 0; i--) {	//大顶堆
		down(arr,len,i);
	}
	
	for (i = len-1; i>0; i--) {	//逐次将最大值放到数组末尾，调整为降序数组
		swap(arr[0],arr[i]);	
		down(arr, i, 0);	//长度递减
	}
}

void main()
{
	int i,a[]={13,50,27,-1,70,10,33,82,100,29,5,14,33,50};
	int len = sizeof(a)/sizeof(a[0]);
	heap_sort(a,len);
	for(i=0; i<len; i++)
		printf("%d ", a[i]);
}
